581F - Zublicanes and Mumocrates - CodeForces Solution

/* Oon commento looloo bord */

#include <bits/stdc++.h>

using namespace std;

const int N = 5'000 + 7, INF = 1'000'000'000;

int n, dp[2][N][N], nl[N], tmp[2][N];
vector<int> adj[N];

void read_input() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

void update(int v, int u) {
    for (int i = 0; i <= nl[v] + nl[u]; i++)
        tmp[0][i] = tmp[1][i] = INF;
    for (int i = 0; i <= nl[v]; i++)
        for (int j = 0; j <= nl[u]; j++)
            for (int colv: {0, 1})
                for (int colu: {0, 1})
                    tmp[colv][i + j] = min(tmp[colv][i + j], dp[colv][v][i] + dp[colu][u][j] + (colv != colu));
    for (int i = 0; i <= nl[v] + nl[u]; i++)
        for (int id: {0, 1})
            dp[id][v][i] = tmp[id][i];
}

void dfs(int v, int par = -1) {
    if ((int) adj[v].size() == 1) {
        nl[v] = 1;
        dp[1][v][1] = dp[0][v][0] = 0;
    }
    else
        dp[1][v][0] = dp[0][v][0] = 0;
    for (int u: adj[v])
        if (u != par) {
            dfs(u, v);
            update(v, u);
            nl[v] += nl[u];
        }
}

int main() {
    memset(dp, 63, sizeof dp);
    read_input();
    dfs(0);
    cout << min(dp[0][0][nl[0] / 2], dp[1][0][nl[0] / 2]) << endl;
}